package greed;

import java.io.*;
import java.util.*;

public class HuffmanCode {
    //huffman编码 key:huffman编码  value:字符ASCII码
    static HashMap<String, Integer> huffmanCode = new HashMap<>();
    //huffman编码 key:字符ASCII码  value:huffman编码
    static HashMap<Integer, String> huffmanCode2 = new HashMap<>();
    static int lastLen;
    static int lastNum;
    public static void main(String[] args) throws IOException {
        String inputFile = "C:\\Users\\H\\Desktop\\huffman\\input.txt";
        String outputFile = "C:\\Users\\H\\Desktop\\huffman\\output.txt";
        String outputFile2 = "C:\\Users\\H\\Desktop\\huffman\\output1.txt";
        long s = System.currentTimeMillis();
        //获取文件字符的频率 key:字符ASCII码  value:字符频率
        HashMap<Integer, Integer> charWeight = getCharWeight(inputFile);
        //创建huffman树
        Node root = createTree(charWeight);
        //输出huffman编码
        System.out.println("字符\tASCII码\t频率\thuffman编码");
        printHuffmanCode(root, "");
        //文件编码
        coding(inputFile, outputFile);
        //文件解码
        decoding(outputFile, outputFile2);
        long e = System.currentTimeMillis();
        System.out.println(e-s);
    }

    /**
     * 创建huffman树
     *
     * @param charWeight 字符频率 key:字符ASCII码  value:字符频率
     * @return huffman树的根结点
     */
    public static Node createTree(HashMap<Integer, Integer> charWeight) {
        //创建保存叶子结点的列表
        ArrayList<Node> tree = new ArrayList<>();
        charWeight.forEach((k, v) -> {
            tree.add(new Node(v, k, null, null));
        });
        //构造Huffman树
        while (tree.size() != 1) { //当列表中只剩下一个结点的时候则退出循环
            //根据树的权重进行排序
            Collections.sort(tree, Comparator.comparingInt(o -> o.weight));
            //将排序后的列表中取前面两个最小的树的结点进行合并
            //权重为该两个结点的权重和，左孩子为最小权重的结点，右孩子为次小权重的结点
            //重新构造一颗树结点，将该结点加到原来的列表当中
            //然后，将最小的两个结点从列表中移除
            tree.add(new Node(tree.get(0).weight + tree.get(1).weight, -1, tree.get(0), tree.get(1)));
            tree.remove(tree.get(0));
            tree.remove(tree.get(0));
        }
        //返回列表中的第一个结点，即为该Huffman树的根结点
        return tree.get(0);
    }

    /**
     * 先序遍历Huffman树
     *
     * @param root huffman树根结点
     * @param code huffman编码
     */
    public static void printHuffmanCode(Node root, String code) {
        if (root != null) {
            if (root.lchild == null && root.rchild == null) {
                huffmanCode.put(code, root.asc);
                huffmanCode2.put(root.asc, code);
                String msg = (char) root.asc + "\t" + root.asc + "\t\t" + root.weight + "\t" + code;
                System.out.println(msg);
            }
            printHuffmanCode(root.lchild, code + "0");
            printHuffmanCode(root.rchild, code + "1");
        }
    }

    /**
     * 对文件进行编码
     *
     * @param inputFile  编码文件
     * @param outputFile 保存编码后的文件
     * @throws IOException
     */
    public static void coding(String inputFile, String outputFile) throws IOException {
        //编码文件
        FileInputStream inputStream = new FileInputStream(inputFile);
        //保存编码后的文件
        DataOutputStream outputStream = new DataOutputStream(new FileOutputStream(outputFile));
        int read;
        //编码后的字符串
        StringBuilder codingContent = new StringBuilder();
        int n=31;//01字符串转为十进制的位数
        int num;//十进制数
        while ((read=inputStream.read())!=-1){
            String s = huffmanCode2.get(read);//获取该ASCII码对应的huffman编码
            codingContent.append(s);//将huffman加入到codingContent中
            if (codingContent.length()>=n){
                num = Integer.valueOf(codingContent.substring(0,n),2);// 截取31位01字符串转为十进制
                outputStream.writeInt(num);//将十进制数字写入文件
                codingContent.delete(0,n);//删除已经转为十进制的01字符串
            }
        }
        //处理最后一个不足31位的01字符串
        num = Integer.valueOf(codingContent.substring(0,codingContent.length()),2);
        outputStream.writeInt(num);
        lastNum = num;//最后一个不足31位的01字符串转为十进制的数字
        lastLen = codingContent.length();//最后一个不足31位的01字符串的长度
        outputStream.close();
    }

    /**
     * 文件解码
     *
     * @param inputFile  解码文件
     * @param outputFile 解码后的文件
     * @throws IOException
     */
    public static void decoding(String inputFile, String outputFile) throws IOException {
        DataInputStream dis = new DataInputStream(new FileInputStream(inputFile));
        int a;//文件读取的十进制数字
        int l;//十进制数字转为二进制后的长度与31位的差值
        StringBuilder coding = new StringBuilder();//编码字符串
        StringBuilder s;// 保存二进制的字符串
        while (dis.available()>0){
            a = dis.readInt();
            s = new StringBuilder(Integer.toBinaryString(a));//将读取的十进制数转为二进制
            //若十进制数字转为二进制后的长度不等于31，则在该二进制数前面补充l个0
            if (a==lastNum){//处理最后一个二进制数
                l = lastLen-s.length();
                for (int i = 0; i < l; i++) {
                    s.insert(0,"0");
                }
            }else if ((l=31-s.length())!=0){
                for (int i = 0; i < l; i++) {
                    s.insert(0,"0");
                }
            }
            coding.append(s);//将二进制字符串加入到编码字符串中
        }
        //临时字符串
        StringBuilder str = new StringBuilder();
        //解码后的字符串
        StringBuilder decodingContent = new StringBuilder();
        for (int i=0;i<coding.length();i++) {
            str.append(coding.charAt(i));//将字符加入临时字符串中
            //如果临时字符串等于已存在的huffman编码，则将该huffman编码解码为对应的字符
            if (huffmanCode.containsKey(str.toString())) {
                String s1 = String.valueOf((char) huffmanCode.get(str.toString()).intValue());//将ASCII码转为char,再将char转为String
                decodingContent.append(s1);//将解码后的字符加到decodingContent字符串中
                str.delete(0, str.length());//删除临时字符串
            }
        }
        //解码后的文件
        FileOutputStream outputStream = new FileOutputStream(outputFile);
        //将解码后的字符串写入到文件中
        outputStream.write(decodingContent.toString().getBytes());
        outputStream.close();
    }

    /**
     * 读取文件统计各个字符出现的频率
     *
     * @param inputFile 编码文件
     * @return 字符的频率 key:字符ASCII码  value:字符频率
     * @throws IOException
     */
    public static HashMap<Integer, Integer> getCharWeight(String inputFile) throws IOException {
        FileInputStream inputStream = new FileInputStream(inputFile);
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int[] b = new int[256];
        int read;
        while ((read = inputStream.read()) != -1) {
            b[read] += 1;
        }
        for (int i = 0; i < b.length; i++) {
            if (b[i] != 0) {
                hashMap.put(i, b[i]);
            }
        }
        return hashMap;
    }
}

/**
 * Huffman树结点类
 */
class Node {
    int weight; //权重
    int asc; //该结点的字符ACll码
    Node lchild; //左孩子
    Node rchild;  //右孩子

    //构造方法
    public Node(int weight, int asc, Node lchild, Node rchild) {
        this.weight = weight;
        this.asc = asc;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}